package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/5 9:01
 * @description :8道
 * 早上三四节计算机体系结构，中午吃了个米饭，晚上吃了驴蹄子面（涨价了），取了个家里寄来的快递，平平淡淡的一天，时间走的太快太快。握在手中却流失于指缝。
 * persevere to last
 * 2021.11.05
 */
public class t20211105 {


    //1218.最长定差子序列
    public int longestSubsequence(int[] arr, int difference) {
        if (arr.length == 1) return 1;

        //int slow = 0, fast = 1;
        int res = 1;

        /*while (slow < arr.length) {

            if (arr[fast] - arr[slow] == difference) {
                int temp = arr[fast];
                int count = fast + 1;
                while (count < arr.length && arr[count] - temp == difference) {
                    temp = arr[count];
                    count++;
                }
                if(count>=arr.length){
                    res = Math.max(res, count - slow);
                    break;
                }
                res = Math.max(res, count - slow);
            } else {
                slow++;
                fast++;
            }

        }*/


        for (int slow = 0; slow < arr.length; slow++) {
            for (int fast = slow + 1; fast < arr.length; fast++) {

                if (arr[fast] - arr[slow] == difference) {
                    int temp = arr[fast];
                    int count = fast + 1;
                    int number = 2;
                    while (count < arr.length) {
                        if (arr[count] - temp == difference) {
                            number++;
                            temp = arr[count];
                            count++;
                        } else {
                            count++;
                        }


                    }

                    res = Math.max(res, number);
                }

            }
        }

        return res;
    }

    public int longestSubsequence2(int[] arr, int difference) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = arr.length;
        int[][] dp = new int[len][2];

        dp[0][1] = 1;
        map.put(arr[0], 0);

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = 1;

            int preValue = arr[i] - difference;
            if (map.containsKey(preValue)) {
                dp[i][1] = Math.max(dp[i][1], dp[map.get(preValue)][1] + 1);
            }
            map.put(arr[i], i);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }

    //45.跳跃游戏2
    public int jump(int[] nums) {
    /*

    题目说明：假设你总是可以到达数组的最后一个位置。
    即一定存在一条路线能够到达最后一个位置，而不是说中间没有 0 ，只是存在可以越过 0 的路线

    贪心算法：找能跳的最远的
    使用 k 记录目前能够跳到的最高位置
    使用 end 记录这次跳跃的边界，到达边界就跳跃次数 + 1

    过程解析：
    最开始遍历 i = 0, end = 0,因此 step 会进行 step ++，我们可以认为，这是开始起跳，因为必定会落下，因此跳跃次数 + 1
    而 nums[0] 这个数限制了你只能在落脚在某个范围内，假如 nums[0] = 4，那么你只能选择落脚在 [1, 4] 位置，而如果到了边界，那么肯定是一次新的起跳，因此次数需要再 + 1

    从 0 位置开始起跳，你落脚的必定是 [1, 4] 位置中能够跳得更远的，因为根据贪心思想，这样做能够尽可能的减少跳跃次数，因为更加接近最后一个位置
    而在这个过程遍历 [1, 4] 过程中一直记录着最远位置 k，而你落地在 [1, 4] 之间，落地的那个点也就是 [1, 4] 之间最能够跳得远的那个位置，因此当到达边界的时候，将 end 更新为 k

    注意：[1, 4] 跳得最远的位置必定不会在 [1, 4] ，因为如果在 [1, 4] ，那么表示根本就出不去 [1, 4] 这个圈
    当然不会是 [4,1,1,1,0,1,2] 这种的，因为如果是这种的，压根过不去这个 0，因此必定第一次起跳必定能够跳出 [1, 4] 这个范围，比如 [4,1,1,1,1,1,0]
        */
        int step = 0,
                maxStep = 0,
                end = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            maxStep = Math.max(maxStep, i + nums[i]);
            if (i == end) {
                step++;
                end = maxStep;
            }

        }

        return step;
    }


    //62.不同路径
    public int uniquePaths(int m, int n) {
        if (m == 1 && n == 1) {
            return 1;
        }

        //创建dp二维数组
        int[][] dp = new int[m][n];

        //dp[i][j] 表示从（0,0）到（i,j）的路径数

        //将第一行的所有元素都设为1，因为位于第一行的元素，从（0,0）只有向右一条路
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        //将第一列的所有元素都设为1，因为位于第一列的元素，从（0,0）只有向下一条路
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        //对dp数组进行填充
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }

    //面试题10.09 排序矩阵查找
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;

        for (int i = rows - 1; i >= 0; i--) {
            if (matrix[i][columns - 1] < target) {
                break;
            }
            if (matrix[i][0] > target) {
                continue;
            }

            int left = 0, right = columns - 1;
            while (left <= right) {
                int mid = left + right >>> 1;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (target > matrix[i][mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }


        }

        return false;
    }

    //面试题10.11 峰与谷
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }


        int[] temp = Arrays.copyOf(nums, nums.length);
        Arrays.sort(temp);

        int left = 0, right = temp.length - 1, index = 0;
        while (left < right) {
            nums[index++] = temp[right--];
            nums[index++] = temp[left++];
        }

        if (nums.length % 2 > 0)
            nums[index] = temp[left];


    }


    //面试题16.01 交换数字
    public int[] swapNumbers(int[] numbers) {
        int[] temp = Arrays.copyOf(numbers, numbers.length);
        numbers[0] = temp[1];
        numbers[1] = temp[0];
        return numbers;
    }

    public int[] swapNumbers2(int[] numbers) {
        numbers[0] ^= numbers[1];
        numbers[1] ^= numbers[0];
        numbers[0] ^= numbers[1];
        return numbers;
    }

    //面试题16.04 井字游戏
    public String tictactoe(String[] board) {

        int heng,//横线和
                zong,//纵线和
                left = 0,//左斜线
                right = 0,//右斜线
                len = board.length;
        boolean flag = false;


        for (int i = 0; i < len; i++) {
            heng = 0;
            zong = 0;

            for (int j = 0; j < len; j++) {
                heng += board[i].charAt(j);
                zong += board[j].charAt(i);

                if (board[i].charAt(j) == ' ') {
                    flag = true;
                }

            }

            //横纵检查
            if (heng == 'X' * len || zong == 'X' * len) return "X";
            if (zong == 'O' * len || heng == 'O' * len) return "O";

            //斜线处理
            left = left + (int) board[i].charAt(i);
            right = right + board[i].charAt(len - i - 1);

        }

        //斜线检查
        if (left == 'X' * len || right == 'X' * len) return "X";
        if (left == 'O' * len || right == 'O' * len) return "O";

        if (flag) {
            return "Pending";
        }

        return "Draw";
    }

    public static void main(String[] args) {
        t20211105 t20211105 = new t20211105();
        int[] test = {5, 3, 1, 2, 3};
        PriorityQueue<Object> queue = new PriorityQueue<>();


    }

}

//面试题16.02 单词频率
class WordsFrequency {

    private HashMap<String, Integer> map = new HashMap<>();

    public WordsFrequency(String[] book) {
        for (String item : book) {
            map.put(item, map.getOrDefault(item, 0) + 1);

        }

    }

    public int get(String word) {
        return map.getOrDefault(word, 0);
    }


}